//int num[100][100]={0};
int dfs(int** num, int m, int n, int i, int j, int k)
{
    int sum = 0;
    int ret = 1;
    int si = i;
    int sj = j;
    if (i < 0 || i >= m || j < 0 || j >= n || num[i][j] == 1)
    {
        return 0;
    }
    while (si)
    {
        sum += si % 10;
        si /= 10;
    }
    while (sj)
    {
        sum += sj % 10;
        sj /= 10;
    }
    if (sum > k)
    {
        num[i][j] = 1;
        return 0;
    }
    num[i][j] = 1;
    int dx[4] = { 1,0,-1,0 };
    int dy[4] = { 0,-1,0,1 };
    for (int e = 0; e < 4; e++)
    {
        ret += dfs(num, m, n, i + dx[e], j + dy[e], k);
    }
    return ret;
}

int movingCount(int m, int n, int k)
{
    int** num = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++)
    {
        num[i] = (int*)calloc(n, sizeof(int));
    }
    int ret = dfs(num, m, n, 0, 0, k);


    //memset(num,0,100*100*4);
    return ret;
}